//419.甲板上的战舰（岛屿数量）
//https://leetcode.cn/problems/battleships-in-a-board
class Solution {
public:
    int countBattleships(vector<vector<char>>& board) {
        int ret = 0;
        int m = board.size(),n = board[0].size();
        int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
        vector<vector<bool>> vis(m,vector<bool>(n,true));

        function<void(vector<vector<char>>&,int,int)> dfs = 
        [&](vector<vector<char>>& board,int x,int y)
        {
            for(int i = 0;i<4;++i)
            {
                int px = dx[i]+x,py = dy[i]+y;
                if(px>=0&&px<m&&py>=0&&py<n&&vis[px][py]&&board[px][py]=='X')
                {
                    vis[px][py] = false;
                    dfs(board,px,py);
                }
            }
        };

        for(int i = 0;i<m;++i)
            for(int k = 0;k<n;++k)
            {
                if(board[i][k] == 'X' && vis[i][k])
                {
                    ++ret;
                    vis[i][k] = false;
                    dfs(board,i,k);
                }
            }

        return ret;
    }
};